package leetcode每日一题.leetcode20212;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 *
 */
@SuppressWarnings("all")
public class Q009_寻找数组中的第k大的元素 {
    // 1. 排序法  时间复杂度为O(nlogn)
    public static int getLargestKElement1(int[] nums,int k) {
        Arrays.sort(nums);
        return (k < nums.length) ? nums[k] : nums[nums.length-1];
    }

    // 2. 创建一个长度为k的维护数组，然后扫描nums，修改维护数组,k比较小的时候时间复杂度为O(n)但是k比较大的时后，时间复杂度比较高
    // 可能不如1的直接排序
    // 对于需要动态找寻最大或者最小值的算法，通常都可以使用堆来优化，jdk底层也帮助我们封装了heap的数据结构
    public static int getLargestKElement2(int[] nums,int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>((n1,n2)->n1-n2); // 创建堆
        for (int x : nums) {
            heap.add(x);
            if(heap.size() > k) {
                heap.poll();
            }
        }
        return heap.poll();
    }

    public static void main(String[] args) {
        int[] nums = {7, 5, 15, 3, 17, 2, 20, 24, 1, 9, 12, 8};
        System.out.println(getLargestKElement2(nums, 3));
    }
}
